home *** CD-ROM | disk | FTP | other *** search
/ Apple WWDC 1996 / WWDC96_1996 (CD).toast / Technology Materials / MacApp Release 10 / MacApp Release 10 - HD Ready / Libraries / Core / Includes / UDependencies.h < prev    next >
Encoding:
Text File  |  1996-04-03  |  14.3 KB  |  462 lines  |  [TEXT/MPS ]

  1. // UDependencies.h
  2. // Copyright © 1984-96 by Apple Computer, Inc. All rights reserved.
  3.  
  4. #ifndef __UDEPENDENCIES__
  5. #define __UDEPENDENCIES__
  6.  
  7. // MacApp
  8.  
  9. #ifndef __ULIST__
  10. #include "UList.h"
  11. #endif
  12.  
  13. #ifndef __ULISTITERATOR__
  14. #include "UListIterator.h"
  15. #endif
  16.  
  17. #ifndef __UOBJECT__
  18. #include "UObject.h"
  19. #endif
  20.  
  21. // ANSI
  22.  
  23. #ifndef __LIMITS__
  24. #include <limits.h>
  25. #endif
  26.  
  27. //----------------------------------------------------------------------------------------
  28. /*    Theory of Operation
  29.     -------------------
  30.     
  31.     The dependency relationships are stored in two arrays of triples, where each
  32.     triple contains a primary object, a secondary object and a label. The arrays are
  33.     sorted first by the primary object.
  34.     
  35.     One array, gDependents, contains notifier-dependent relationships, so the primary 
  36.     object is a notifier and the secondary objects are dependents. For example, 
  37.     suppose A has two dependents C and D, each of which has B as a dependent. 
  38.     The dependents array looks as follows:
  39.     
  40.         A    C     label
  41.         A    D     label
  42.         C    B     label
  43.         D    B    label
  44.     
  45.     The other array, gNotifiers, contains dependent-notifier relationships, so the 
  46.     primary object is a dependent and the secondary objects are notifiers:
  47.  
  48.         B    C     label
  49.         B    D     label
  50.         C    A     label
  51.         D    A    label
  52.     
  53.     The labels are used for marking objects, though they may have other uses in future.
  54.     
  55.     Iteration over the secondary objects for a given primary object is performed by 
  56.     doing a binary search for a matching primary object, then iterating backwards to 
  57.     find the beginning of the cluster of entries with that primary object. Iteration then
  58.     proceeds forwards until the primary object changes. To iterate over the dependents of 
  59.     an object we use gDependents, and to iterate over its notifiers we use gNotifiers.
  60.     
  61.     These data structures are not particularly space-efficient, but allow fast iteration 
  62.     over both notifiers and dependents. Each entry is only twelve bytes, so you should be 
  63.     able to have hundreds of dependencies with no problem.*/
  64.  
  65. //----------------------------------------------------------------------------------------
  66.  
  67.  
  68. //----------------------------------------------------------------------------------------
  69. // Constants
  70. //----------------------------------------------------------------------------------------
  71.  
  72. const long kNoLabel = LONG_MAX - 1;
  73.  
  74.  
  75. //----------------------------------------------------------------------------------------
  76. // Typedefs
  77. //----------------------------------------------------------------------------------------
  78.  
  79. typedef long DependencyLabels;
  80.     // The valid range of labels
  81.  
  82. typedef long LabelRange;
  83.     // Used internally because we flip the label's sign to mark an object
  84.  
  85.  
  86. //----------------------------------------------------------------------------------------
  87. // Notification
  88. //----------------------------------------------------------------------------------------
  89.  
  90. struct Notification
  91. {
  92.     inline Notification()
  93.     { };
  94.     
  95.     inline Notification(TObject* notifier,
  96.                  ChangeID theChange,
  97.                  TObject* changedBy) :
  98.     fNotifier(notifier),
  99.     fChange(theChange),
  100.     fChangedBy(changedBy)
  101.     { }        
  102.  
  103.     TObject* fNotifier;
  104.     TObject* fChangedBy;
  105.     ChangeID fChange;
  106. };
  107.  
  108. //----------------------------------------------------------------------------------------
  109. // TNotificationQueue
  110. //----------------------------------------------------------------------------------------
  111.  
  112. class TNotificationQueue : public TDynamicArray
  113. {
  114.     MA_DECLARE_CLASS;
  115.     
  116. public:
  117.  
  118.     inline TNotificationQueue()
  119.     { }
  120.  
  121.     virtual ~TNotificationQueue();
  122.         
  123.     inline void INotificationQueue()
  124.     { IDynamicArray(1, sizeof(Notification)); }
  125.         // Initialize the array
  126.  
  127.     //------------------------------------------------------------------------------------
  128.     // Insertion and Deletion
  129.     //------------------------------------------------------------------------------------
  130.  
  131.     inline void Queue(const Notification& item)
  132.     { InsertElementsBefore(1, (void*) &item, 1); }
  133.         // FIFO queue addition.(same as insertLast)
  134.  
  135.     Boolean Dequeue(Notification& item);
  136.         // FIFO queue relief
  137.  
  138.     //------------------------------------------------------------------------------------
  139.     // static member functions
  140.     //------------------------------------------------------------------------------------
  141. public:
  142.  
  143.     static TNotificationQueue* NewNotificationQueue();
  144.         // Utility function to create a new TNotificationQueue object. 
  145.  
  146. };
  147.  
  148. //----------------------------------------------------------------------------------------
  149. // Dependency
  150. //----------------------------------------------------------------------------------------
  151.  
  152. struct Dependency
  153. {
  154.     inline Dependency(TObject* primaryObject,
  155.                 TObject* secondaryObject,
  156.                 LabelRange dependencyLabel) :
  157.     fPrimaryObject(primaryObject),
  158.     fSecondaryObject(secondaryObject),
  159.     fLabel(dependencyLabel)
  160.     { }
  161.         // Constructor
  162.  
  163.     TObject* fPrimaryObject;
  164.     TObject* fSecondaryObject;
  165.     LabelRange fLabel;
  166. };
  167.  
  168. typedef struct Dependency *DependencyPtr;
  169.  
  170. //----------------------------------------------------------------------------------------
  171. // TDependencies: An array for storing the dependency relationships
  172. //----------------------------------------------------------------------------------------
  173.  
  174. class TDependencies : public TSortedDynamicArray
  175. {
  176.     MA_DECLARE_CLASS;
  177.     
  178. public:
  179.  
  180.     inline TDependencies()
  181.     { }
  182.         // Empty constructor
  183.  
  184.     virtual ~TDependencies();
  185.         // Destructor
  186.         
  187.     inline void IDependencies()
  188.     { ISortedDynamicArray(1, sizeof(Dependency)); }
  189.         // Initialize the array
  190.  
  191.  
  192.     //------------------------------------------------------------------------------------
  193.     // Insertion and Deletion
  194.     //------------------------------------------------------------------------------------
  195.  
  196.     virtual void AddDependency(TObject* primaryObject,
  197.                                       TObject* secondaryObject,
  198.                                       DependencyLabels dependencyLabel);
  199.         // Register an object ("secondaryObject") as dependent on the specified change in
  200.         // another object ("primaryObject")
  201.  
  202.     virtual void InsertDependencyBefore(ArrayIndex index,
  203.                                                TObject* primaryObject,
  204.                                                TObject* secondaryObject,
  205.                                                DependencyLabels dependencyLabel);
  206.         // Add a dependency relation to the array
  207.  
  208.     virtual void RemoveDependency(TObject* primaryObject,
  209.                                          TObject* secondaryObject,
  210.                                          DependencyLabels dependencyLabel);
  211.         // Remove a dependency relation from the array if it is present
  212.  
  213.  
  214.     //------------------------------------------------------------------------------------
  215.     // Searching
  216.     //------------------------------------------------------------------------------------
  217.  
  218.     virtual CompareResult CompareElements(void* Element1, void* Element2);
  219.         // Orders the elements of the array by the ordinal value of the notifier.
  220.  
  221.     virtual Boolean FindDependency(TObject* primaryObject,
  222.                                           TObject* secondaryObject,
  223.                                           DependencyLabels dependencyLabel,
  224.                                           ArrayIndex& index);
  225.         // Returns true if the specified dependency is in the array. The position of the
  226.         // dependency is returned in "index". If the dependency is not present the
  227.         // position at which it should be inserted is returned in "index"
  228.  
  229.     virtual Boolean FindPrimaryObject(TObject* primaryObject, ArrayIndex& index);
  230.         // Returns true if a binary search for the specified primary object succeeds.
  231.         // The index of the found entry is also returned.
  232.  
  233.     inline TObject* PrimaryObjectAt(ArrayIndex i)
  234.     { return ((DependencyPtr)ComputeAddress(i))->fPrimaryObject; }
  235.         // Returns the primary object at a given index
  236.  
  237.     inline TObject* SecondaryObjectAt(ArrayIndex i)
  238.     { return ((DependencyPtr)ComputeAddress(i))->fSecondaryObject; }
  239.         // Returns the secondary object at a given index
  240. };
  241.  
  242. //----------------------------------------------------------------------------------------
  243. // TDependencySpace: Abstract Superclass of Dependency Spaces
  244. //----------------------------------------------------------------------------------------
  245.  
  246. class TDependencySpace : public TObject
  247. {
  248.     MA_DECLARE_CLASS;
  249.     
  250. public:
  251.     inline TDependencySpace()
  252.     { }
  253.         // Empty constructor
  254.  
  255.     virtual ~TDependencySpace();
  256.         // Destructor
  257.     
  258.     inline void IDependencySpace()
  259.     { IObject(); }
  260.         // Initialization method for TDependencySpace
  261.         
  262.     virtual void AddDependency(TObject* notifier,
  263.                                       TObject* dependent,
  264.                                       DependencyLabels dependencyLabel);
  265.         // Register an object ("dependent") as a dependent of another object ("Notifier"),
  266.         // with specified label (can be kNoLabel)
  267.     
  268.     virtual void RemoveDependency(TObject* notifier,
  269.                                          TObject* dependent,
  270.                                          DependencyLabels dependencyLabel);
  271.         // Remove the dependency relation if it is present
  272.     
  273.     virtual void RemoveDependencies(TObject* anObject);
  274.         // Remove all dependencies containing the object, either as Notifier or dependent.
  275.         // Called by TObject::Free.
  276.  
  277.     virtual void NotifierChanged(TObject* notifier,
  278.                                         ChangeID theChange,
  279.                                          TObject* changedBy);
  280.         // Notifies dependents of "notifier" that it has changed
  281.  
  282. };
  283.  
  284. //----------------------------------------------------------------------------------------
  285. // TSimpleDependencySpace: Used by MacApp to store dependency relationships and propagate
  286. // changes to immediate dependents. MacApp has a single global instance gMacAppDependencies
  287. //----------------------------------------------------------------------------------------
  288.  
  289. class TSimpleDependencySpace : public TDependencySpace
  290. {
  291.     MA_DECLARE_CLASS;
  292.     
  293. public:
  294.     TSimpleDependencySpace();
  295.         // Constructor
  296.         
  297.     inline void ISimpleDependencySpace()
  298.     { IDependencySpace(); }
  299.         // Initialize this object
  300.  
  301.     virtual ~TSimpleDependencySpace();
  302.         // Free this object
  303.         
  304.     virtual void AddDependency(TObject* notifier,
  305.                                       TObject* dependent,
  306.                                       DependencyLabels dependencyLabel);    // Override
  307.         // Register an object ("dependent") as a dependent of another object ("Notifier"),
  308.         // with specified label (can be kNoLabel)
  309.     
  310.     virtual void RemoveDependency(TObject* notifier,
  311.                                          TObject* dependent,
  312.                                          DependencyLabels dependencyLabel);    // Override
  313.         // Remove the dependency relation if it is present
  314.  
  315.  
  316.     virtual void RemoveDependencies(TObject* anObject);    // Override
  317.         // Remove all dependencies containing the object, either as Notifier or dependent.
  318.         // Called by TObject::Free.
  319.  
  320.     virtual void NotifierChanged(TObject* notifier,
  321.                                         ChangeID theChange,
  322.                                          TObject* changedBy);    // Override
  323.         // Notifies direct dependents of "notifier" that it has changed
  324.         
  325.     //----------------------------------------------------------------------------------------
  326.     // data members
  327.     //----------------------------------------------------------------------------------------
  328. public:
  329.  
  330.     TDependencies* fDependents;
  331.     TDependencies* fNotifiers;
  332. };
  333.  
  334. //----------------------------------------------------------------------------------------
  335. // TStandardDependencySpace: Can be used to store dependency relationships and propagate
  336. // changes to immediate and indirect dependents. 
  337. //----------------------------------------------------------------------------------------
  338.  
  339. class TStandardDependencySpace : public TSimpleDependencySpace
  340. {
  341.     MA_DECLARE_CLASS;
  342.     
  343. public:
  344.     TStandardDependencySpace();
  345.         // Constructor
  346.     virtual ~TStandardDependencySpace();
  347.         // Destructor
  348.                 
  349.     inline void IStandardDependencySpace()
  350.     { ISimpleDependencySpace(); }
  351.         // Initialize this object
  352.  
  353.     virtual void NotifierChanged(TObject* notifier,
  354.                                  ChangeID theChange,
  355.                                   TObject* changedBy);    // Override
  356.         // Notifies direct and indirect dependents of "notifier" that it has changed
  357.         // Handles nested calls to Changed. 
  358.  
  359.     void NotifyDependents(TObject* notifier,
  360.                           ChangeID theChange,
  361.                           TObject* changedBy);
  362.         // Notifies direct and indirect dependents of "notifier" that it has changed
  363.         // Does not handle nested calls to Changed. 
  364.     
  365.     virtual void MarkAllDependents(TObject* notifier, Boolean state);
  366.         // Marks all the direct and indirect dependents of "notifier"
  367.  
  368.     virtual void MarkObject(TObject* anObject, Boolean state);    // Override
  369.         // Used to mark or unmark an object as needing updating. Used during a change/update
  370.         // phase
  371.     
  372.     virtual Boolean IsObjectMarked(TObject* anObject);    // Override
  373.         // Returns true if the specified object is currently marked
  374.  
  375.     virtual void UpdateMarkedObjects(ChangeID theChange,
  376.                                      TObject* changedObject,
  377.                                      TObject* changedBy);
  378.         // Updates all marked objects by calling HandleUpdate
  379.  
  380.     virtual void HandleUpdate(TObject* anObject,
  381.                               ChangeID theChange,
  382.                               TObject* changedObject,
  383.                               TObject* changedBy);
  384.         // If "anObject" is marked as needing updating, unmark it, update all its notifiers,
  385.         // then update the object itself by calling its DoUpdate method
  386.         
  387.     virtual void UpdateNotifiers(TObject* anObject,
  388.                                  ChangeID theChange,
  389.                                  TObject* changedObject,
  390.                                  TObject* changedBy);
  391.         // Recursively updates each notifier of "anObject"
  392.  
  393.     //----------------------------------------------------------------------------------------
  394.     // data members
  395.     //----------------------------------------------------------------------------------------
  396. public:
  397.     TNotificationQueue*    fNestedUpdates;        // Queue of updates to be processed
  398.     Boolean                fUpdating;            // An update is in progress
  399.  
  400. };
  401.  
  402. //----------------------------------------------------------------------------------------
  403. // Iterators 
  404. //----------------------------------------------------------------------------------------
  405.  
  406. class CDependencyIterator : public CArrayIterator {
  407.   public:
  408.     CDependencyIterator (TDependencies* theArray, TObject* theObject);
  409.       
  410.     virtual ~CDependencyIterator();
  411.     
  412.     void Reset(); // Override
  413.  
  414.     Boolean More();    // Override
  415.     
  416.     TObject* CurrentObject();
  417.     
  418.     TObject* FirstObject();
  419.     
  420.     TObject* NextObject();
  421.  
  422.   protected:
  423.     TObject* fObject;      
  424. };
  425.  
  426. class CDependentIterator : public CDependencyIterator {
  427.   public:
  428.       CDependentIterator (TObject* theObject, TSimpleDependencySpace* dependencySpace);
  429.     
  430.     virtual ~CDependentIterator();
  431.     
  432.     inline TObject* FirstDependent()
  433.     { return FirstObject(); }
  434.     
  435.     inline TObject* NextDependent()
  436.     { return NextObject(); }
  437.  
  438.     inline TObject* CurrentDependent()
  439.     { return CurrentObject(); }
  440. };
  441.  
  442.  
  443. class CNotifierIterator : public CDependencyIterator {
  444.   public:
  445.       CNotifierIterator (TObject* theObject, TSimpleDependencySpace* dependencySpace);
  446.     
  447.     virtual ~CNotifierIterator();
  448.     
  449.     inline TObject* FirstNotifier()
  450.     { return FirstObject(); }
  451.     
  452.     inline TObject* NextNotifier()
  453.     { return NextObject(); }
  454.  
  455.     inline TObject* CurrentNotifier()
  456.     { return CurrentObject(); }
  457. };
  458.  
  459. extern TDependencySpace* gMacAppDependencies;
  460.  
  461. #endif // __UDEPENDENCIES__
  462.